Search

A multi-modal search space can be defined as having multiple attraction basins – each basin has a single local optimum which is reached from all points in that basin when greedy local search is used. Optimization in multi-modal search spaces can then be viewed as a two-phase process. The first phase is exploration in which the most promising attraction basin is identified. The second phase is exploitation in which the best solution (i.e. the local optimum) within the previously identified attraction basin is attained. The goal of thresheld convergence is to improve the performance of search techniques during the first phase of exploration. The effectiveness of thresheld convergence has been demonstrated through applications to existing metaheuristics such as particle swarm optimization and differential evolution, and through the development of novel metaheuristics such as minimum population search and leaders and followers.

Computer modeling of protein ligand interactions is one of the most important phases in a drug design process. Part of the process involves the optimization of highly multi-modal objective (scoring) functions. This research presents the Minimum Population Search heuristic as an alternative for solving these global unconstrained optimization problems. To determine the effectiveness of Minimum Population Search, a comparison with seven state-of-the-art search heuristics is performed. Being specifically designed for the optimization of large scale multi modal problems, Minimum Population Search achieves excellent results on all of the tested complexes, especially when the amount of available function evaluations is strongly reduced. A first step is also made toward the design of hybrid algorithms based on the exploratory power of Minimum Population Search. Computational results show that hybridization leads to a further improvement in performance.

El cómputo de alto rendimiento es una necesidad para el desarrollo de investigaciones con grandes volúmenes de datos. La creciente demanda de este tipo de resultados ha impulsado a varios centros de investigación a poner en funcionamiento recursos de cómputo de alto rendimiento. En Cuba no existe una solución definitiva que permita a todos los centros de investigación disponer de los recursos de cómputo necesarios para desarrollar sus proyectos. Este trabajo propone el empleo de un clúster de computadoras de la Universidad de Griffith a través de una interfaz basada en el correo electrónico. Esta solución permite disponer de recursos de cómputo de alto rendimiento sin necesidad de una alta conectividad. Como caso de estudio se analizan los resultados obtenidos en un proyecto de optimización global en grandes dimensiones desarrollado en la Universidad de La Habana. Para experimentos con un mes de duración (en una computadora estándar) los resultados muestran que al utilizar el recurso de alto rendimiento es posible alcanzar un incremento en el rendimiento relativo superior al 1300%.

Minimum Population Search is a recently developed metaheuristic for optimization of mono-objective continuous problems, which has proven to be a very effective optimizing large scale and multi-modal problems. One of its key characteristic is the ability to perform an efficient exploration of large dimensional spaces. We assume that this feature may prove useful when optimizing multi-objective problems, thus this paper presents a study of how it can be adapted to a multi-objective approach. We performed experiments and comparisons with five multi-objective selection processes and we test the effectiveness of Thresheld Convergence on this class of problems. Following this analysis we suggest a Multi-objective variant of the algorithm. The proposed algorithm is compared with multi-objective evolutionary algorithms IBEA, NSGA2 and SPEA2 on several well-known test problems. Subsequently, we present two hybrid approaches with the IBEA and NSGA-II, these hybrids allow to further improve the achieved results.

Spanish abstract Los problemas lineales con restricciones de equilibrio son un caso particular de los modelos de optimización con restricciones de equilibrio. Debido a la complejidad que presentan, la condición de equilibrio se sustituye por condiciones necesarias obteniéndose un problema con restricciones de complementariedad (MPCC). La estructura del conjunto de soluciones factibles del MPCC obtenido es compleja ya que es la unión de poliedros. Resolver todos los problemas correspondientes a minimizar la función objetivo sobre cada uno de estos poliedros es computacionalmente costoso. El presente trabajo utiliza un enfoque heurístico para dar solución al MPCC, adaptando los algoritmos de Búsqueda Local y Recocido Simulado. Este trabajo presenta un conjunto de funciones de prueba y los resultados computacionales más significativos obtenidos. English abstract Linear equilibrium constrained programming is a special class of optimization models with equilibrium constraints. Because of the complexity of the equilibrium condition it is replaced by necessary conditions, which leads to a complementarity constrained problem (MPCC). The set of feasible solutions in a MPCC is structured as a union of polyhedrons. Solving the MPCC problem would require the minimization of the objective function on each of these polyhedrons. The computation cost of this approach is unfeasible, thus, this work presents a new approach where heuristic algorithms such as Hill Climbing and Simulated Annealing are used to search for good solutions on the polyhedrons space. A new benchmark for linear equilibrium constrained optimization is introduced. The computational results achieved by the proposed heuristics on the new benchmark are presented.

A multi-modal search space can be defined as having multiple attraction basins – each basin has a single local optimum which is reached from all points in that basin when greedy local search is used. Optimization in multi-modal search spaces can then be viewed as a two-phase process. The first phase is exploration in which the most promising attraction basin is identified. The second phase is exploitation in which the best solution (i.e. the local optimum) within the previously identified attraction basin is attained. The goal of thresheld convergence is to improve the performance of search techniques during the first phase of exploration. The effectiveness of thresheld convergence has been demonstrated through applications to existing metaheuristics such as particle swarm optimization and differential evolution, and through the development of novel metaheuristics such as minimum population search and leaders and followers.

Computer modeling of protein-ligand interactions is one of the most important phases in a drug design process. Part of the process involves the optimization of highly multi-modal objective (scoring) functions. This research presents the Minimum Population Search heuristic as an alternative for solving these global unconstrained optimization problems. To determine the effectiveness of Minimum Population Search, a comparison with seven state-of-the-art search heuristics is performed. Being specifically designed for the optimization of large scale multi-modal problems, Minimum Population Search achieves excellent results on all of the tested complexes, especially when the amount of available function evaluations is strongly reduced. A first step is also made toward the design of hybrid algorithms based on the exploratory power of Minimum Population Search. Computational results show that hybridization leads to a further improvement in performance.

Resumen El cómputo de alto rendimiento es una necesidad para el desarrollo de investigaciones con grandes volúmenes de datos. La creciente demanda de este tipo de resultados ha impulsado a varios centros de investigación a poner en funcionamiento recursos de cómputo de alto rendimiento. En Cuba no existe una solución definitiva que permita a todos los centros de investigación disponer de los recursos de cómputo necesarios para desarrollar sus proyectos. Este trabajo propone el empleo de un clúster de computadoras de la Universidad de Griffith a través de una interfaz basada en el correo electrónico. Esta solución permite disponer de recursos de cómputo de alto rendimiento sin necesidad de una alta conectividad. Como caso de estudio se analizan los resultados obtenidos en un proyecto de optimización global en grandes dimensiones desarrollado en la Universidad de La Habana. Para experimentos con un mes de duración (en una computadora estándar) los resultados muestran que al utilizar el recurso de alto rendimiento es posible alcanzar un incremento en el rendimiento relativo superior al 1300%. Abstract: Research with large volumes of data usually require access to High Performance Computing. The increasing demand for this kind of research has led many institutions to develop their own computer clusters. However, in Cuba there is no definitive solution for the High Performance Computing requirements of institutions such as the University of Havana. The expenses of building a computer cluster disallows many institutions to have their own, while the low connectivity limits the use of international high performance computing services. This research presents an alternative solution based on the development of an email-based platform for accessing a computer cluster at Griffith University in Australia. This new communication interface has been successfully used on a Large Scale Optimization research project at the University of Havana. Computational results show that by using the remote cluster it is possible to improve upon the performance of a personal computer by up to 1300%.

Minimum Population Search is a recently developed metaheuristic for optimization of mono- objective continuous problems, which has proven to be a very effective optimizing large scale and multi-modal problems. One of its key characteristic is the ability to perform an efficient exploration of large dimensional spaces. We assume that this feature may prove useful when optimizing multi objective problems, thus this paper presents a study of how it can be adapted to a multi-objective approach. We performed experiments and comparisons with five multi-objective selection processes and we test the effectiveness of Thresheld Convergence on this class of problems. Following this analysis we suggest a Multi-objective variant of the algorithm. The proposed algorithm is compared with multi-objective evolutionary algorithms IBEA, NSGA2 and SPEA2 on several well-known test problems. Subsequently, we present two hybrid approaches with the IBEA and NSGA-II, these hybrids allow to further improve the achieved result.

Los problemas lineales con restricciones de equilibrio son un caso particular de los modelos de optimización con restricciones de equilibrio. Debido a la complejidad que presentan, la condición de equilibrio se sustituye por condiciones necesarias obteniéndose un problema con restricciones de complementariedad (MPCC). La estructura del conjunto de soluciones factibles del MPCC obtenido es compleja ya que es la unión de poliedros. Resolver todos los problemas correspondientes a minimizar la función objetivo sobre cada uno de estos poliedros es computacionalmente costoso. El presente trabajo utiliza un enfoque heurístico para dar solución al MPCC, adaptando los algoritmos de Búsqueda Local y Recocido Simulado. Este trabajo presenta un conjunto de funciones de prueba y los resultados computacionales más significativos obtenidos.